﻿using Solution;
using System.Text;

namespace CSLearn
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            Backtrack backtrack = new Backtrack();
            DP dp = new DP();
            Greedy greedy = new Greedy();
            Graph graphTheory = new Graph();
            TreeNode treeNode = new TreeNode();
            while (true)
            {
                Console.WriteLine("\n准备开始:");
                Console.WriteLine("1. 继续测试");
                Console.WriteLine("其他: 结束程序");
                string choice = Console.ReadLine();
                if (!choice.Equals("1"))
                {
                    break;
                }
                Console.WriteLine("继续测试, 请输入: ");

                //Console.WriteLine("请输入整数 m n ");
                //Console.Write("m = ");
                //int m = int.Parse(Console.ReadLine());
                //Console.Write("n = ");
                //int n = int.Parse(Console.ReadLine());

                //Console.WriteLine("请输入一维整型数组 ");
                //string[] stringnums = Console.ReadLine().Split(' ');
                //int[] nums = new int[stringnums.Length];
                //for (int i = 0; i < stringnums.Length; i++)
                //{
                //    nums[i] = int.Parse(stringnums[i]);
                //}
                //greedy.MinIncrements(n, nums);




                //Console.WriteLine("请输入二维整型数组 (1 2 3,4 5 6,7 8 9) ");
                //string[] stringNums = Console.ReadLine().Split(',');
                //int row = stringNums.Length;
                //int col = stringNums[0].Split(' ').Length;
                //int[][] arrs = new int[row][];
                //for (int i = 0; i < row; i++)
                //{
                //    string[] numsReally = stringNums[i].Split(' ');
                //    arrs[i] = new int[col];
                //    for (int j = 0; j < col; j++)
                //    {
                //        arrs[i][j] = int.Parse(numsReally[j]);
                //    }
                //}


                //Console.WriteLine("调用核心代码: 684  冗余连接");
                //Console.WriteLine(graphTheory.FindRedundantDirectedConnection(arrs));
            }
            //HertaInput();
            JianMuInput();
        }

        static int[] h, e, next;
        static int n, x, index = 0, count; // index为下标，count记录满足条件的节点个数
        static HashSet<int> s = new HashSet<int>();

        // 添加一条边 a->b的一条边
        static void Add(int a, int b)
        {
            e[index] = b;
            next[index] = h[a];
            h[a] = index++;
        }

        static void DFS(int u, int father, int n)
        {
            Console.WriteLine($"DFS({u}, {father}, {n})");
            s.Add(u);
            for (int i = u; i <= n; i += u)
            {
                Console.WriteLine($"s.Contains({i})");
                if (s.Contains(i)) count++;
            }
            for (int i = h[u]; i != 0; i = next[i])
            {
                int v = e[i];
                Console.WriteLine($"{v} != {father}");
                if (v != father) DFS(v, u, n);
            }
            s.Remove(u);
        }

        static void JianMuInput()
        {
            string[] firstInput = Console.ReadLine().Split(' ');
            n = int.Parse(firstInput[0]);
            x = int.Parse(firstInput[1]);
            h = new int[2 * n + 1];
            e = new int[2 * n + 1];
            next = new int[2 * n + 1];

            for (int i = 1; i < n; i++)
            {
                string[] stringInput = Console.ReadLine().Split(' ');
                int u = int.Parse(stringInput[0]);
                int v = int.Parse(stringInput[1]);
                Add(u, v);
                Add(v, u);
            }
            DFS(x, 0, n);
            Console.WriteLine("输出结果: " + count);
            Console.WriteLine("index: " + index);
        }

        // 黑塔转圈圈
        static void HertaInput()
        {
            int t = int.Parse(Console.ReadLine());
            while (t-- > 0)
            {
                int n = int.Parse(Console.ReadLine());
                string[] stringnums = Console.ReadLine().Split(' ');
                int[] nums = new int[stringnums.Length];
                for (int i = 0; i < stringnums.Length; i++)
                {
                    nums[i] = int.Parse(stringnums[i]);
                }
                string[] stringDamage = Console.ReadLine().Split(' ');
                int e = int.Parse(stringDamage[0]);
                int r = int.Parse(stringDamage[1]);
                Herta(n, nums, e, r);
            }
        }

        static void Herta(int n, int[] h, int e, int r)
        {
            int countE = 0;
            int countR = 0;
            Array.Sort(h);
            for (int i = 0; i < n; i++)
            {
                long cur = h[i] - e * countE - r * countR;
                if (cur + cur <= h[i])
                {
                    countR++;
                }
                else
                {
                    long temp = cur - h[i] / 2;
                    countE += (int)((temp + e - 1) / e);
                    countR++;
                }
            }
            long last = h[n - 1] - e * countE;
            if (last - r * countR > 0)
            {
                countE += (int)((last - r * countR + e - 1) / e);
            }
            else
            {
                int nr = (int)((last + r - 1) / r);
                countR = Math.Min(countR, nr);
            }
            Console.WriteLine("本组结果:  " + countE + " " + countR);
        }
    }
}